package com.lfc.arrayandstring;

import java.util.*;

/**
 * 数组和字符串算法相关专题
 * 整个解题步骤，封装method-(n)的静态方法，配合main函数测试，method方法中主要封装了一些该算法流程的测试
 * 用例
 */
public class Test {
    public static void main(String[] args) {
//        method01();
//        method02();
//        method03();
//        method04();
//        method05();
//        method06();
//        method07();
//        method10();
//        method11();
//        method12();
        // 符号
//        method13();
//        method14();
//        method15();
//        method16();
//        method17();
        method18();
    }

    private static void method01() {
        int matrix[][] = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
        int target = 20;
        System.out.println(findNumberIn2DArray(matrix, target));
    }

    /**
     * 查找二维数组中存在的数字
     *
     * @param matrix
     * @param target
     * @return 真 存在，假，不存在
     */
    private static boolean findNumberIn2DArray(int matrix[][], int target) {
        /**
         * 解题思路：
         * 1.判断target在matrix是否存在，只需要遍历这个数据，如果存在返回真，不存在返回假，
         * 2.无论是从左上角到右下角遍历，还是从左下角到右上角遍历取值判断都可以
         * 3.小于就往右边一列,大于就往上边一行
         */
        int row = 0, col = matrix.length - 1;
        // 设置循环的边界条件，递减的col行数大于0，递增的row小于矩阵的列数
        while (col >= 0 && row < matrix[0].length) {
            // 获取
            int m = matrix[col][row];
            if (m == target) {
                return true;
            } else if (m > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }

    private static void method02() {
        String s = "We are happy.";
        System.out.println(replaceSpace(s));
    }

    /**
     * 将字符串中的空格替换成%20
     *
     * @param s
     * @return
     */
    private static String replaceSpace(String s) {
        /**
         * 解题思路使用字符串拼接的方式使用到StringBuilder,或者可以直接拼接字符串
         * 增加一个新字符串，遍历原来的字符串，遍历过程中，
         * 如果非空格则将原来的字符直接拼接到新字符串中，如果遇到空格则将%20拼接到新字符串中
         */
//        s.replaceAll(" ","%20");
//        StringBuilder builder = new StringBuilder();
//        for (int i = 0; i < s.length(); i++) {
//            if (s.charAt(i) == ' ') {
//                builder.append("%20");
//            } else {
//                builder.append(s.charAt(i));
//            }
//        }
//        return builder.toString();
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == ' ') res += "%20";
            else res += ch;
        }
        return res;
    }

    private static void method03() {
//      int arr[]={3,4,5,1,2};
        int arr[] = {2, 2, 2, 0, 1};
        System.out.println(minArray(arr));
    }

    /**
     * 解题思路：首先数组是一个有序数组的旋转，从这个条件可以看出，数组是有大小规律的，可以使用二分查找利用存在的规律快速找出结果
     *
     * @param nums
     * @return
     */
    private static int minArray(int[] nums) {
        /**
         * 解题思路
         * 1.初始化下标l,r
         * 2.每次计算中间下标 mid=l+r>>>1;
         * 3.当nums[mid] < nums[r]时，说明此时的数据最小值在[left,mid]之间，则令r=mid,进行下一步的计算
         * 4.ums[mid]=nums[r] ,无法判断最小值在哪个区间中，此时让r--,缩小区间范围，进行下一轮的判断
         *  因为是升序数组，所以最小值在数组的左侧，而不是右侧
         */
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >>> 1;
            if (nums[mid] < nums[r]) {
                r = mid;
            } else if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                r--;
            }
        }
        return nums[l];
    }

    public static void method04() {
        int n = 3;
        int[] ints = printNumbers(n);
        System.out.println(Arrays.toString(ints));

    }

    public static int[] printNumbers(int n) {
        int sum = 1;
        for (int i = 0; i < n; i++) sum *= 10;
        int[] ints = new int[sum - 1];
        for (int i = 0; i < sum - 1; i++) ints[i] = i + 1;
        return ints;
    }

    private static void method05() {
        int arr[] = {1, 2, 3, 4};
        int[] ints = exchange(arr);
        System.out.println(Arrays.toString(ints));

    }

    private static int[] exchange(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        int res[] = new int[n];
        for (int i = 0; i < n; i++) {
            int m = arr[i];
            if ((m & 1) == 1) res[l++] = m;
            else res[r--] = m;
        }
        return res;
    }

    private static void method06() {
        int matrix[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[] ints = spiralOrder(matrix);
        System.out.println(Arrays.toString(ints));

    }

    private static int[] spiralOrder(int[][] matrix) {
        // 获取二维数组的行数
        int m = matrix.length;
        // 获取二维数组的列数
        int n = matrix[0].length;
        // 设置要返还的数组
        int res[] = new int[m * n];
//        int res[] = new int[n];

        // 设置四个指针，分别是左右上下
        int l = 0, r = n - 1, t = 0, b = m - 1, x = 0;
        // 测试获取指定的列
//        for (int i = 0; i <= b; i++) res[x++] = matrix[i][0];
        // 获取指定的行
//        for (int i = 0; i < n; i++) res[x++] = matrix[0][i];

        while (true) {
            // 先遍历从左到右，添加到返回的数组中
            for (int i = l; i <= r; i++) res[x++] = matrix[t][i];
            if (++t > b) break;
            // 从上到下
            for (int i = t; i <= b; i++) res[x++] = matrix[i][r];
            if (l > --r) break;
            // 从右到左
            for (int i = r; i >= l; i--) res[x++] = matrix[b][i];
            if (t > --b) break;
            // 从下到上
            for (int i = b; i >= t; i--) res[x++] = matrix[i][l];
            if (++l > r) break;
        }
        return res;
    }

    private static void method07() {
//        int arr[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        int arr[] = {1, 1, 2, 3, 4, 5, 6};
        System.out.println(majorityElement(arr));
    }

    /**
     * 数组中出现最多次数字
     *
     * @param arr
     * @return
     */
    private static int majorityElement(int arr[]) {
        // 理解方法1；先排序，直接取中位数
//        Arrays.sort(arr);
//        return arr[arr.length/2];
        // 另一种解决思路：抵消的方式
        //1.
        int cur = 0, count = 0;
        for (int art : arr) {
            if (count == 0) cur = art;
            int i = art == cur ? count++ : count--;
        }
        return cur;
    }

    private static void method08() {
        int arr[] = {10, 2};
        System.out.println(minNumber(arr));
    }

    private static String minNumber(int arr[]) {
        /**
         * 1.将数组转换成字符串，放入到字符串数组中，
         * 2.在对放入集合中的字符串按照指定规则进行排序
         * 3.对按指定规则排序后的字符串拼接起来
         */
        List<String> list = new ArrayList<>();
        for (int num : arr) list.add(String.valueOf(num));
        list.sort((a, b) -> (a + b).compareTo(b + a));
        String res = "";
        for (String s : list) res += s;
        return res;
    }

    private static void method09() {
        int arr[] = {5, 7, 7, 8, 8, 10};
        int target = 8;
        System.out.println(search(arr, target));
    }

    /**
     * 查找数组中的指定的数字
     *
     * @param arr
     * @param target
     * @return
     */
    public static int search(int arr[], int target) {
        /**
         * 解题思路：主要是采用二分查找的方式
         */
        return getmethed(arr, target) - getmethed(arr, target - 1);
    }

    private static int getmethed(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + r >>> 1;
            if (arr[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    private static void method10() {
        int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 9};
        System.out.println(missingNumber(arr));
    }

    public static int missingNumber(int arr[]) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = l + r >>> 1;
            if (arr[mid] == mid) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    public static void method11() {
        int matrix[][] = {{5, 2, 4}, {3, 0, 5}, {0, 7, 2}};
        int target = 3;
        System.out.println(numberOfPaths(matrix, target));
    }

    /**
     * 矩阵中能被k整除的路径个数
     *
     * @param grid
     * @param k
     * @return
     */
    public static int numberOfPaths(int[][] grid, int k) {
        int mod = (int) (1e9 + 7);
        int m = grid.length, n = grid[0].length;
        int[][][] f = new int[m + 1][n + 1][k];
        f[0][1][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int v = 0; v < k; v++) {
                    f[i + 1][j + 1][(v + grid[i][j]) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % mod;
                }
            }
        }
        return f[m][n][0];
    }

    public static void method12() {
        int arr[] = {2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(twoSum(arr, target)));
    }

    public static int[] twoSum(int arr[], int target) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            if (arr[l] + arr[r] == target) return new int[]{arr[l], arr[r]};
            else if (arr[l] + arr[r] > target) r--;
            else l++;
        }
        return new int[0];
    }

    private static void method13() {
        int[] startIme = {1, 2, 3, 4, 6};
        int[] endTime = {3, 5, 10, 6, 9};
        int[] profit = {20, 20, 100, 70, 60};
        System.out.println(jobScheduling(startIme, endTime, profit));
    }

    /**
     * 描述: 计算工资的最大值
     *
     * @param startTime 其实时间数组
     * @param endTime   结束时间数据
     * @param profit    当天的工资数
     * @return int 返回计算所得的最大值
     * @author lfc
     */
    private static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        /**
         * 解题思路：使用动态规划+二分查找
         * 1.使用动态规划的方式解决
         * 使用结束时间的数组按照正序排列，使dp[i]表述前前i份兼职工资，
         * 可以获得最大报酬，初始化dp[0]=0,对于i>0则满足下面表达式
         * dp[i]=max(dp[i-1],dp[k]+profit[i-1])
         * 其中k表示满足结束时间小于等于第i-1份开始时间的工作数量，可以通过二分查找的方式获得
         */
        int n = startTime.length;
        int jobs[][] = new int[n][];
        for (int i = 0; i < n; i++) jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[1]));
        for (int i = 0; i < jobs.length; i++) {
            for (int j = 0; j < jobs[0].length; j++) {
                System.out.print(jobs[i][j] + ",");
            }
            System.out.println();
        }
        int dp[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            // 找出k值
            int k = binarySearch(jobs, i - 1, jobs[i - 1][0]);
            dp[i] = Math.max(dp[i - 1], dp[k] + jobs[i - 1][2]);
        }
        return dp[n];
    }

    private static int binarySearch(int[][] jobs, int r, int target) {
        int l = 0;
        while (l < r) {
            int mid = l + r >>> 1;
            if (jobs[mid][1] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private static void method14() {
        int target = 9;
        int[][] arr2D = findContinuousSequence(target);
        for (int[] ints : arr2D) {
            for (int i : ints) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
    }

    /**
     * 和为s的连续子数列
     *
     * @param target
     * @return
     */
    private static int[][] findContinuousSequence(int target) {
        int l = 1, r = 2;
        List<int[]> list = new ArrayList<>();
        while (l < r) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; i++) {
                    res[i - l] = i;
                }
                list.add(res);
                l++;
            } else if (sum < target) r++;
            else l++;

        }
        return list.toArray(new int[list.size()][]);
    }

    private static void method15() {
        String s = "the sky is blue";
        System.out.println(reverseWords(s));
    }

    /**
     * 单词翻转，设置两个指针，翻转从字符串的最后一个位开始，一旦检测到空格，就将此空格替换掉
     *
     * @param s
     * @return
     */
    public static String reverseWords(String s) {
        String trim = s.trim();
        int start = trim.length() - 1;
        int end = trim.length() - 1;
        String res = "";
        while (start >= 0) {
            while (start >= 0 && trim.charAt(start) != ' ') start--;
            res += trim.substring(start + 1, end + 1) + " ";
            while (start >= 0 && trim.charAt(start) == ' ') start--;
            end = start;
        }
        return res;
    }

    private static void method16() {
        int[] res = {1, 2, 3, 4, 5};
        System.out.println(isStraight(res));
    }

    public static boolean isStraight(int[] nums) {
        int len = nums.length;
        if (len != 5) return false;
        int jkcnt = 0;
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            // 先判断，同时防止数组溢出
            if (nums[i] != 0 && i != len - 1) {
                if (nums[i] == nums[i + 1])
                    return false;
            }
            // 统计0的个数
            if (nums[i] == 0) jkcnt++;
        }

        return nums[len - 1] - nums[jkcnt] < 5;
    }

    public static void method17() {
        int arr[] = {1, 2, 3, 4, 5};
        int[] arrs = constructArr(arr);
        for (int i : arrs) System.out.print(i + ",");
    }

    private static int[] constructArr(int nums[]) {
        int n = nums.length;
        int dp[] = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) dp[i] = dp[i - 1] * nums[i - 1];
        for (int j = n - 2, sum = 1; j >= 0; j--) {
            sum *= nums[j + 1];
            dp[j] *= sum;
        }
        return dp;
    }

    private static void method18() {
        int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] ints = maxSlidingWindow(arr, 3);
        System.out.println(Arrays.toString(ints));

    }

    /**
     * 计算滑动窗口的最大值
     *
     * @param nums
     * @param
     * @return
     */
    public static int[] maxSlidingWindow(int nums[], int k) {
//        // 排除边界条件
//        int n=nums.length;
//        if (n == 0 || k == 0) return new int[0];
//        Deque<Integer> queue = new LinkedList<>();
//        int res[] = new int[n - k + 1];
//        for (int r = 0, l = 1 - k; l < n; l++, r++) {
//            // 判断队列为null 情况
//            if (l > 0 && queue.peekFirst() == nums[l - 1]) queue.removeFirst();
//            while (!queue.isEmpty() && queue.peekLast() < nums[r]) queue.removeLast();
//            queue.addLast(nums[r]);
//            if (l >= 0) res[l] = queue.peekFirst();
//        }
//        return res;
        if (nums == null || nums.length < 2) return nums;
        // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
        Deque<Integer> queue = new LinkedList();
        // 结果数组
        int[] res = new int[nums.length - k + 1];
        // 遍历nums数组
        for (int i = 0; i < nums.length; i++) {
            // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
                queue.pollLast();
            }
            // 添加当前值对应的数组下标
            queue.addLast(i);
            // 判断当前队列中队首的值是否有效
            if (queue.peek() <= i - k) {
                queue.poll();
            }
            // 当窗口长度为k时 保存当前窗口中最大值
            if (i + 1 >= k) {
                res[i + 1 - k] = nums[queue.peek()];
            }
        }
        return res;
    }

    /**
     * a-z返回最长字符串
     *
     * @param s
     * @return
     */
    private static int maxStringsum(String s) {
        if (s.equals(" ")&& s.length() == 0) return 0;
        // 将一个字符串转换为char类型的数组
        char[] str = s.toCharArray();
        int[] dp = new int[26];
//        int[] ins = new int[128];
        Arrays.fill(dp, -1);
        int res = 0, stat = 0;
        dp[str[0] - 'a'] = 0;
        for (int i = 1; i < str.length; i++) {
            stat = Math.min(i - dp[str[i] - 'a'], stat + 1);
            res = Math.max(res, stat);
            dp[str[i] - 'a'] = i;
        }
//        for (int i = 0; i < n; i++) {
//            int idx = s.charAt(i);
//            stat = Math.max(stat, ins[idx] + 1);
//            res = Math.max(res, i - stat + 1);
//            ins[idx] = i;
//        }


        return res;
    }


}
